/*
https://leetcode.cn/problems/number-of-provinces/description
并查集
*/
class UnionFind {
public:
    vector<int> p;  // 父节点数组
    int n;  // 节点数量

    // 构造函数，初始化并查集
    UnionFind(int x) {
        n = x;
        p.resize(n);  // 根据节点数量调整父节点数组的大小
        for (int i = 0; i < n; i++) {
            p[i] = i;  // 初始时每个节点的父节点是自己
        }
    }

    // 查找操作，找到 x 的根节点，并进行路径压缩
    int find(int x) {
        if (x == p[x]) {
            return x;  // 如果 x 的父节点是自己，说明 x 是根节点
        }
        return p[x] = find(p[x]);  // 路径压缩，将 x 的父节点直接指向根节点
    }

    // 合并操作，将 x 和 y 所在的集合合并
    void Union(int x, int y) {
        p[find(x)] = find(y);  // 将 x 的根节点的父节点设置为 y 的根节点
    }

    // 计算当前有多少个独立的集合
    int count() {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (p[i] == i) {
                cnt++;  // 如果 p[i] 是自己，说明 i 是一个集合的根节点
            }
        }
        return cnt;
    }
};